A sphere is one of the fundamental graphic primitive shapes employed in three-dimensional (3-D) computer graphics that are commonly used in computer games, simulations, and other types of virtual environments. Although dramatic advances have recently been made in developing powerful graphics hardware and engines to render 3-D computer graphics in realtime, new approaches that reduce the processing overhead required for generating primitive shapes such as spheres are very much desired, so that the available processing capabilities of the central processing unit (CPU) and graphics processors can be more efficiently employed for other purposes. The geometry of spheres and other primitive shapes is either directly expressed as a collection of triangles, or through the control points of a higher order surface, which must itself be tessellated into triangles by the rendering engine early in the graphics pipeline processing. Accordingly, a sphere is normally approximated by a set of triangles with shared edges and, ideally, having vertices evenly distributed over the surface of the sphere. One of the geometric forms best suited to the approximation of a sphere using polygons is a geodesic dome, as shown in FIG. 2A. The geodesic dome shown in this Figure is constructed from a subdivided icosahedron and has 252 vertices that define the corners of 500 triangles. When rendered using diffuse light with Gouraud shading, the result is shown in FIG. 2B. To construct a geodesic dome like that shown in FIG. 2A from one of the regular polyhedra, polygons comprising the base geometry of any of the five Platonic solids are reiteratively subdivided in a triangulation process. Each of the polygons in the polyhedron are subdivided into a number of small polygons, and the resulting vertices of the polygons are projected out to a radius equal to that of the polyhedron's original vertices. The smaller polygons are subdivided again, and the process is reiterated until the resulting geometry satisfactorily approximates a sphere for the purposes of the graphic application in which the sphere is to be used. Thus, this reiterative process creates n geodesic domes of various complexities to arrive at a final dome of order n, applying the geodesation operation on each intermediate dome in turn, to achieve greater tessellation.
Although the process described above is straightforward and effective, it has its drawbacks. By its nature, this process lends itself to the use of recursive functions calls, which have a clear inherent processing cost, due to increased call overhead, additional storage requirements for function state, and the repetitive nature of the method. This prior art process must construct intermediate geodesic domes during each successive pass to subdivide the polygons comprising each intermediate dome. Accordingly, a substantial up-front memory allocation must be made to store all of the intermediate geodesic domes, or memory must be allocated at every reiterative pass, or a very high frequency of smaller memory allocations and memory freeing operations must be performed at the polygon level to divide individual triangles of the intermediate domes. The single allocation and per-pass allocation of memory reserve much more memory that is actually required to construct the final geodesic dome. The per-triangle allocations of memory are much better at conserving memory, but they sacrifice performance and cause memory fragmentation. Also, the multi-pass approach for generating a geodesic dome is computationally slow, not only because it must generate successive intermediate geodesic domes, but also because the per-triangle subdivisions can lead to redundant calculation of vertex locations for subdivided triangles, where a calculated vertex location along the edge of one triangle might be recalculated for an adjacent triangle that shares the edge.
To avoid the problems noted above, the geometry of the desired geodesic dome can be pre-computed and then loaded for rendering by a graphics engine when needed. However, in many applications, it will not be possible to pre-compute the required geometry for a geodesic dome. In addition, the storage requirements for a densely modeled sphere can be relatively significant. For example, a geodesic dome formed from an icosahedron with a tessellation order of 64 contains over 40,000 vertices and 490,000 indices. By generating a sphere at runtime instead of pre-computing it, the storage of the pre-computed geometry data is avoided. Instead, it is only necessary to store the origin, radius, and tessellation order of the sphere as input to the sphere generation process. Additionally, to provide a performance enhancement, there is a clear need for an approach that enables the spherical geometry to be computed in less time than required for loading the equivalent amount of pre-computed geometry data for the sphere from a file.
To avoid recursive or multi-pass subdivisions of a geodesic dome, a simpler method of subdivision can be employed, so that the repositioning of polygons between each subdivision is postponed, and by performing the polygon subdivision and vertex projections as discrete steps. Each polygon of a polyhedron is first completely subdivided into a final set of smaller polygons that will form the geodesic dome. After the subdivisions, all polygons have the same edge lengths and lie completely within the planes of the original polyhedral faces. The vertices of these polygons are then gnomonically projected en masse to a distance from the center of the polyhedron equal to that of the original vertices. Thus, this iterative approach is much faster than performing successive subdivisions of intermediate geodesic domes and simplifies the entire process for non-power-of-two tessellation orders. However, in postponing the gnomonic projections of polygons until after all subdivisions have taken place, this approach sacrifices the uniformity of vertex distribution on the surface of the geodesic dome. Instead, the uniformity of distribution lies on the surface of the original polyhedron and is lost during the projection process. Vertices located nearer to the corners of the original polyhedron will end up closer to one another in the resulting dome than those located close to the center of the original faces. Since the geodesic dome produced will less closely resemble a sphere than that which could have been constructed through the more conventional recursive process, additional vertices must be added with a higher tessellation order to compensate for the uneven distribution of vertices. For this reason, a still different approach is required that achieves equal distribution of vertices, but enables a polyhedron to be efficiently subdivided in a single pass, without the need to construct intermediate geodesic domes.